package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KLinkedList;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * TODO 多练
 * 143. 重排链表
 * https://leetcode.cn/problems/reorder-list/
 *
 * 输入: head = [1,2,3,4]
 * 输出: [1,4,2,3]
 * 链表中点、链表翻转、链表合并
 */
@KLinkedList
@XClassic
public class LC143_ReorderList {
    public static void main(String[] args) {
        // ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
        // Utils.printLinkedList(head);
        new Solution2().reorderList(head);
        // Utils.printLinkedList(head);
    }

    /**
     *
     */
    static
    class Solution {
        public void reorderList(ListNode head) {
            // 0 判断空链表，直接返回
            if(head == null) {
                return;
            }

            // 1 寻找中间点
            ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
            while (fast != null && fast.next != null) {
                fast = fast.next;
                slow = slow.next;
                if(fast.next != null) {
                    fast = fast.next;
                }
            }

            // 2 获得第二部分链表
            ListNode secondHead = slow.next;
            slow.next = null;

            // 3 翻转第二部分链表
            secondHead = reverseList(secondHead);

            // 4 第一部分与第二部分链表连接操作
            ListNode prev = dummy;
            while (head != null && secondHead != null) {
                ListNode tmp = head.next;

                prev.next = head;
                head.next = secondHead;
                prev = secondHead;

                head = tmp;
                secondHead = secondHead.next;
            }

            if(head != null) {
                prev.next = head;
            }
        }

        private ListNode reverseList(ListNode head) {
            ListNode prev = null, current = head;
            while (current != null) {
                ListNode next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            return prev;
        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public void reorderList(ListNode head) {
            // 0 寻找中间节点
            ListNode mid = middleNode(head);
            // 1 翻转中间下半断链表
            ListNode head2 = reverseList(mid);
            // 2 交叉合并
            while (head2.next != null) {
                ListNode next = head.next, next2 = head2.next;
                head.next = head2;
                head2.next = next;
                head = next;
                head2 = next2;
            }
        }

        /**
         * 找到链表的中间节点
         * @param head
         * @return
         */
        private ListNode middleNode(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        /**
         * 反转链表
         * @param head
         * @return
         */
        private ListNode reverseList(ListNode head) {
            ListNode pre = null, cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    }

    @XOptimal
    static
    class Solution2 {
        public void reorderList(ListNode head) {
            // 0 寻找中间点
            ListNode middle = findMiddle(head);
            Utils.printLinkedList(head);
            // 1 翻转后半部
            ListNode reversed = reverseList(middle);
            Utils.printLinkedList(reversed);
            Utils.printLinkedList(head);
            // 2 交叉在一起
            head = mixLists(head, reversed);
            Utils.printLinkedList(head);
        }

        private ListNode findMiddle(ListNode head) {
            ListNode slow = head, fast = head;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        private ListNode reverseList(ListNode head) {
            ListNode prev = null, current = head;
            while (current != null) {
                ListNode next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            return prev;
        }

        private ListNode mixLists(ListNode head1, ListNode head2) {
            ListNode p1 = head1, p2 = head2;
            while (p2.next != null) {
                ListNode next1 = p1.next, next2 = p2.next;
                p1.next = p2;
                p2.next = next1;
                p1 = next1;
                p2 = next2;
            }
            return head1;
        }
    }
}
